package utils;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Utils {
	public static long maxIntAsLong = Integer.MAX_VALUE;
	
	public static boolean isPrime(long n) {
		if (n < 1) {
			throw new IllegalArgumentException(""+n);
		}
		if (n == 1) {
			return false;
		}
		if (n < 4) {
			return true;
		}
		if (n % 2 == 0) {
			return false;
		}
		if (n < 9) {
			return true;
		}
		if (n % 3 == 0) {
			return false;
		}
		
		//Any number n can have only one primefactor greater than sqrt(n).
		//The consequence for primality testing of a number n is: if we cannot find a number f less than
		//or equal sqrt(n) that divides n then n is prime: the only primefactor of n is n itself
		long r = (long) Math.sqrt(n);

		//All primes greater than 3 can be written in the form 6k+/-1.
		for (int f = 5; f <= r; f += 6) {
			if (n % f == 0) {
				return false;
			}
			if (n % (f+2) == 0) {
				return false;
			}
		}
		
		return true;
	}

	private static final Map<Long, Boolean> cache = new HashMap<Long, Boolean>();
	public static boolean isPrimeCached(long n) {
		if (cache.containsKey(n)) {
			return cache.get(n);
		}
		cache.put(n, isPrime(n));
		if (cache.size() % 1000000 == 0) {
			System.out.println("Cache size reached " + cache.size());
		}
		return cache.get(n);
	}
	
	public static List<Long> primeFactors(long number) {
		List<Long> result = new ArrayList<Long>();
		addPrimeFactors(number, result);
		return result;
	}
	
	private static void addPrimeFactors(long number, List<Long> list) {
		if (number < 2) {
			return;
		}
		if (number % 2 == 0) {
			list.add(2L);
			addPrimeFactors(number/2, list);
			return;
		}
		for(long i = 3; i <= number; i+=2) {
			if (number % i == 0) {
				list.add(i);
				addPrimeFactors(number/i, list);
				return;
			}
		}
	}

	public static long product(Collection<Long> list) {
		long result = 1;
		for (long number : list) {
			result *= number;
		}
		return result;
	}
	
	public static Long sum(Collection<Long> collection) {
		Long result = 0L;
		for (Long number : collection) {
			result += number;
		}
		return result;
	}
	
	public static long sumOfIntegers(Collection<Integer> collection) {
		long result = 0;
		for (long number : collection) {
			result += number;
		}
		return result;
	}
	
	public static List<Long> allPrimesUnder(int upperBound) {
		ArrayList<Long> list = new ArrayList<Long>();
		
		for (int prime : sieve(upperBound)) {
			list.add((long)prime);
		}
		
		return list;
	}

	public static List<List<Long>> subsets(List<Long> source, int setSize) {
		List<List<Long>> subsets = new ArrayList<List<Long>>();

		//TODO implement
		
		return subsets;
	}

	public static List<Integer> first(int n) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			list.add(i);
		}
		return list;
	}

	public static int sumForNumbers(final String source) {
		return stringSum(source, 48);
	}
	
	public static int sumForUppercaseChars(final String source) {
		return stringSum(source, 64);
	}

	private static int stringSum(final String source, final int offset) {
		int sum = 0;
		for (int i = 0; i < source.length(); i++) {
			sum += source.charAt(i) - offset;
		}
		return sum;
	}

	public static int product(String source) {
		int product = 1;
		for (char c : source.toCharArray()) {
			product *= c - 48;
		}
		return product;
	}

	public static List<Integer> sieve(int upperBound) {
		int crossLimit = (int) Math.sqrt(upperBound) + 1;
		boolean[] sieve = new boolean[upperBound];
		sieve[0] = true;
		sieve[1] = true;
		
		for (int n = 4; n < upperBound; n += 2) {
			sieve[n] = true;
		}
		for (int n = 3; n < crossLimit; n += 2) {
			if (!(sieve[n])) {
				for (int m = n*n; m < upperBound; m += 2*n) {
					sieve[m] = true;
				}
			}
		}
		
		List<Integer> list = new ArrayList<Integer>();
		for (int n = 0; n < upperBound; n++) {
			if (!sieve[n]) {
				list.add(n);
			}
		}
		return list;
	}
	
	public static BigInteger faculteit(long base) {
		BigInteger result = BigInteger.ONE;
		for (; base > 1; base--) {
			result = result.multiply(BigInteger.valueOf(base));
		}
		return result;
	}

	public static List<Integer> divisors(int number) {
		List<Integer> result = new ArrayList<Integer>();
		for (int i = 1; i <= (number/2)+1; i++) {
			if (number % i == 0) {
				result.add(i);
			}
		}
		return result;
	}
	
	public static void printProgress(long current, long amount) {
		System.out.printf("Progress: %.2f%%%n", current/(double)amount*100);
	}

	public static void printProgress(long current, long amount, long startTime) {
		final double prc = current/(double)amount;
		long runTime = System.currentTimeMillis() - startTime;
		System.out.printf("Progress: %.2f%%, expected run time %d ms%n", prc*100, (long)(runTime / prc));
	}

	public static boolean isPalindrome(long number) {
		return isPalindrome(Long.toString(number));
	}

	public static boolean isPalindrome(final String text) {
		final int length = text.length();
		
		for (int i = 0; i < length/2; i++) {
			if (text.charAt(i) != text.charAt(length - i - 1)) {
				return false;
			}
		}
		return true;
	}
	
    public static boolean isPandigital(String digits, int n) {
    	if (n == 0 || n > 9) {
    		throw new IllegalArgumentException();
    	}
    	
		if (digits.length() != n) {
			return false; 
		}
		for (int i = 1; i <= n; i++) {
			if (digits.indexOf(i+48) == -1) {
				return false;
			}
		}
		return true;
	}
    
    public static void permutate(String prefix, char[] charArray, Collection<String> set) {
		if (charArray.length == 1) {
			set.add(prefix + charArray[0]);
		}
		else {
			for (int index = 0; index < charArray.length; index++) {
				permutate(prefix + charArray[index], remove(index, charArray), set);
			}
		}
	}

    private static char[] remove(int index, char[] charArray) {
		char[] newArray = new char[charArray.length - 1];
		for (int i = 0; i < charArray.length; i++) {
			if (i != index) {
				newArray[(i < index ? i : i-1)] = charArray[i];
			}
		}
		return newArray;
	}

    /**
     * @param fileName name of the file
     * @return a {@link Scanner} reading from the file name specified
     * @throws NullPointerException if the file doesn't exist in the resources package
     */
	public static Scanner getScannerForFile(String fileName) {
		return new Scanner(ClassLoader.getSystemResourceAsStream("resources/" + fileName));
	}
	
	public static Iterable<Character> charIterable(String s) {
		final String string = s.toUpperCase();
		return new Iterable<Character>() {
			@Override
			public Iterator<Character> iterator() {
				return new Iterator<Character>() {
					private int count = 0;

					@Override
					public boolean hasNext() {
						return count < string.length();
					}

					@Override
					public Character next() {
						return string.charAt(count++);
					}

					@Override
					public void remove() {
						throw new UnsupportedOperationException();
					}
				};
			}
		};
	}

	/**
	 * Iterates over the digits of i
	 */
	public static Iterable<Integer> numberIterable(long i) {
		final String string = Long.toString(i);
		return new Iterable<Integer>() {
			@Override
			public Iterator<Integer> iterator() {
				return new Iterator<Integer>(){
					private int count = 0;

					@Override
					public boolean hasNext() {
						return count < string.length();
					}

					@Override
					public Integer next() {
						return string.charAt(count++) - 48;
					}

					@Override
					public void remove() {
						throw new UnsupportedOperationException();
					}
				};
			}
		};
	}

	public static BigInteger combinations(int n, int r) {
		if (r < 0 || r > n) {
			throw new IllegalArgumentException();
		}
		if (r == 0 || r == n) {
			return BigInteger.ONE;
		}
		return faculteit(n).divide(faculteit(r).multiply(faculteit(n-r)));
	}
	
	public static boolean isTriangle(int a, int b, int c) {
		return a*a + b*b == c*c;
	}
	
	public static boolean coprime(int a, int b) {
		return gcd(a, b) == 1;
	}
	
	public static long gcd(long a, long b) {
		if (a < b) 
			return gcd(b,a);
		if (a % b != 0)
			return gcd(b, a%b);
		return b;
	}

	public static int sumOfDigits(long n) {
		int sum = 0;
		String value = Long.toString(n);
		for (int i = 0; i < value.length(); i++) {
			sum += value.charAt(i)-48;
		}
		return sum;
	}

	public static int sumOfDigits(BigInteger n) {
		int sum = 0;
		String value = n.toString();
		for (int i = 0; i < value.length(); i++) {
			sum += value.charAt(i)-48;
		}
		return sum;
	}
}
